package org.forever.util
{
	/**
	* （有向）图的广度优先遍历算法模板
	*/
	public class BFS extends GraphTraverse
	{
		public function BFS(g:Graph)
		{
			super(g);
		}
		
		/**广度优先遍历算法*/
		override protected function traverse( s:Vertex,  info:Object):Object {//从顶点s出发，做广度优先查找
			if (UNDISCOVERED != s.getStatus())	return null;//跳过已访问过的顶点（针对非连通图）
			var Q:Queue = new Queue_List();//借用一个队列
			s.setStatus(DISCOVERED);//发现s后
			Q.enqueue(s);//随即令其入队
			visit(s, null);//并访问之
			while (!Q.isEmpty()) {//在队列变空之前
				var v:Vertex = Q.dequeue() as Vertex;//取出队首顶点v
				for (var it:Iterator = v.getOutEdges(); it.hasNext();) {//检查与顶点v
					var e:Edge = (Edge)it.getNext();//通过边e = (v, u)
					var u:Vertex = (Vertex)e.getVPosInV(1).getElem();//相联的每一顶点u
					if (UNDISCOVERED == u.getStatus()) {//若u尚未被发现，则
						e.setType(TREE);//将e归类为树边
						u.setStatus(DISCOVERED);//发现u后
						Q.enqueue(u);//随即令其入队
						visit(u, v);//并访问之
					} else {//若u已被发现，甚至已访问完毕（有向图），则
						e.setType(CROSS);//将e归类为跨边
					}
				}//至此，v的所有邻居都已访问结束，故
				v.setStatus(VISITED);//将v标记为VISITED
			}//while
			return null;
		}
		
	}
}